package solution.list;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a> check:
 *         http://www.sureinterview.com/shwqst/717001/715001
 */
public class BunksInCircle {
	/**
	 * http://www.sureinterview.com/shwqst/717001/715001
	 * 
	 * @param travleInfo
	 *            the array for the bunks and distances
	 * @return staring position
	 */
	int getStartPos(int[][] travleInfo) {
		int startPos = 0;
		int ttlLegs = travleInfo.length;

		int ttlPetrol = 0; // accumulated fuel.
		int distanceToTravle = 0; // total distance.
		int curPos = startPos;
		// or loop for ttlLengts times: for (int i = 0; i < ttlLegs; i++)
		do {
			if (ttlPetrol >= distanceToTravle) {
				// can move to another bunk
				ttlPetrol += travleInfo[curPos][0];
				distanceToTravle += travleInfo[curPos][1];
				curPos = (curPos + 1) % ttlLegs;
			} else {
				// cannot move any more. need to borrow some fuel by moving
				// starting point backwards.
				startPos = (startPos + ttlLegs - 1) % ttlLegs;
				ttlPetrol += travleInfo[startPos][0];
				distanceToTravle += travleInfo[startPos][1];
			}
		} while (curPos != startPos);

		return startPos;
	}

	/**
	 * http://www.sureinterview.com/shwqst/717001/715001
	 * 
	 * @param travleInfo
	 *            the array for the bunks and distances
	 * @return staring position
	 */
	int getStartPos2(int[][] travleInfo) {
		int startPos = 0;
		int ttlLegs = travleInfo.length;

		int ttlPetrol = 0;
		int distanceToTravle = 0;
		int curPos = startPos;
		for (int i = 0; i < ttlLegs; i++) {
			if (ttlPetrol >= distanceToTravle) {
				// can move on.
				ttlPetrol += travleInfo[curPos][0];
				distanceToTravle += travleInfo[curPos][1];
				curPos = (curPos + 1) % ttlLegs;
			} else {
				// those passed station does not contain the staring point.
				// set the starting point to next new station.
				startPos = curPos;
				ttlPetrol = 0;
				distanceToTravle = 0;
			}
		}

		return startPos;
	}

	@Test
	public void test() {
		int[][] p = new int[][] {
				//
				{ 0, 1 }, //
				{ 2, 1 }, //
				{ 2, 1 }, //
				{ 1, 1 }, //
				{ 0, 1 }, //
		};

		for (int j = 0; j < 5; j++) {
			int t[] = p[0];
			for (int i = 0; i < p.length - 1; i++) {
				p[i] = p[i + 1];
			}
			p[p.length - 1] = t;

			Assert.assertEquals(getStartPos(p), getStartPos2(p));
		}
	}
}
